package DoblePointer;//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 10⁴ 
// 0 <= height[i] <= 10⁵ 
// 
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 2834 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class trap {
    public int trap(int[] height) {
        /**
         * 三指针解决，top指针指向最高位置，然后对两边分别进行双指针计算
         * */
        int n =height.length;
        //特殊情况
        if(n<3){
            return 0;
        }

        int max = Integer.MIN_VALUE;
        int maxIdx = 0;
        //找到最大位置下标
        for (int i = 0; i < n; i++) {
            if(height[i]>max){
                max = height[i];
                maxIdx = i;
            }
        }

        /***
         * 观察问题特点可得，在最高点左侧，当左指针比右指针大时，能存水，因为最高点肯定比他们高，
         * 左右指针的差值即存水量，此时右指针右移，（等于的情况一并处理，因为相等时，差值为0，不影响）
         * 当左指针小于右指针时，说明这之间存不了水,令左指针等于右指针，
         * */
        int sum = 0;
        //先计算最高位置左边
        int left = 0,right = 0;
        while(right<maxIdx){
            if(height[left]>=height[right]){
                sum +=  height[left] - height[right];
                right++;
            }else{
                left=right;
            }
        }
        /**
         * 右边的情况和左边相反，从两个指针指向末尾，当左指针小于或等于右指针时，记录差值，左指针左移
         * 否则 右指针指向左，
         * */
        //计算最高位置右边
        left = n-1;
        right = n-1;
        while(left>=maxIdx){
            if(height[left]<=height[right]){
                sum +=  height[right] - height[left];
                left--;
            }else{
                right=left;
            }
        }
        return sum;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
